UVa/10099 - The tourist guide/10099.cpp

   1 #include <iostream>
   2 #include <map>
   3 #include <set>
   4 #include <vector>
   5 #include <queue>
   6 #include <algorithm>
   7 #include <climits>
   8
   9 using namespace std;
  10
  11 typedef int node;
  12 typedef pair<int, pair<node, node> > edge;
  13 typedef map<node, vector<edge> > graph;
  14
  15 vector<int> maximum;
  16 graph g;
  17
  18 int maxCapacity(const node& start, const node& destiny){
  19   priority_queue<edge> q(g[start].begin(), g[start].end());
  20   set<node> visited;
  21   visited.insert(start);
  22   while (!q.empty()){
  23     edge e = q.top();
  24     q.pop();
  25     node w = e.second.second;
  26     if (visited.count(w) == 0){
  27       maximum[w] = min(maximum[w], min(e.first, maximum[e.second.first]));
  28       if (w == destiny){
  29         return maximum[w];
  30       }
  31       visited.insert(w);
  32       vector<edge> neighbors = g[w];
  33       for (int i=0; i<neighbors.size(); ++i){
  34         q.push(neighbors[i]);
  35       }
  36     }
  37   }
  38   return -1;
  39 }
  40
  41 int main(){
  42   int n, r, c = 1;
  43   while (cin >> n >> r && n > 0 && r > 0){
  44     maximum = vector<int>(n+1, INT_MAX);
  45     g.clear();
  46     while (r--){
  47       int x, y, d;
  48       cin >> x >> y >> d;
  49       g[x].push_back( edge(d, make_pair(x, y)) );
  50       g[y].push_back( edge(d, make_pair(y, x)) );
  51     }
  52
  53     node start, destiny;
  54     int people;
  55     cin >> start >> destiny >> people;
  56     cout << "Scenario #" << c++ << endl;
  57     if (start == destiny){
  58       cout << "Minimum Number of Trips = 0" << endl;
  59     }else{
  60       cout << "Minimum Number of Trips = ";
  61       int result = 0;
  62       int temp = maxCapacity(start, destiny);
  63       while (people > 0){
  64         people -= temp - 1;
  65         ++result;
  66       }
  67       cout << result << endl;
  68       //cout << "MaxCapacity: " << maxCapacity(start, destiny) << endl;
  69     }
  70     cout << endl;
  71   }
  72   return 0;
  73 }